package ljl.alg.wangzheng_camp.round1.dp;

public class _416_can_part {

    /**
     * 他说这个 dp[i][j] 状态含义是对于下标 0..i 有没有若干个数和为 j？
     * 我日，这个若干，我蒙了！
     *
     * 状态压缩后，dp[0] 含义是如何能让数字和为 0，答案是不选
     *
     * 他说排序然后找规律之类的很容易找出反例，做不出来的
     * 只能动态规划？
     *
     * 这个题很难！
     *
     * */
    static class dp2 {
        public boolean canPartition(int[] nums) {
            int sum = 0, max = 0;
            for (int num : nums) {
                sum += num;
                max = Math.max(max, num);
            }
            if (sum % 2 != 0) return false;
            int half = sum / 2;
            if (half < max) return false;
            boolean[] dp = new boolean[half + 1];
            dp[0] = true;
            for (int num : nums) {
                for (int i = half; i >= num; i--) {
                    dp[i] |= dp[i - num];
                }
            }
            return dp[half];
        }
    }
}
